package euclidean

import (
	"math"
	"sort"
)

type tNormalGcdCalculator struct {
}

func newNormalGcdCalculator() IGCDCalculator {
	return &tNormalGcdCalculator{}
}


func (me *tNormalGcdCalculator) Calc(a, b int) int {
	if a <= 0 || b <= 0 {
		return 1
	}

	if a == b {
		return a
	}

	aa := me.split(a)
	sort.Sort(sort.IntSlice(aa))

	bb := me.split(b)
	sort.Sort(sort.IntSlice(bb))

	for i, j := len(aa) - 1, len(bb) - 1;i >= 0 && j >= 0; {
		if aa[i] == bb[j] {
			return aa[i]
		}

		if aa[i] > bb[j] {
			i--
		} else {
			j--
		}
	}

	return 1
}

func (me *tNormalGcdCalculator) split(a int) []int {
	to := int(math.Floor(math.Sqrt(float64(a))))
	items := make([]int, 0)
	for i := 1;i <= to;i++ {
		if a % i == 0 {
			items = append(items, i)
			items = append(items, a / i)
		}
	}
	return items
}

var NormalGCDCalculator = newNormalGcdCalculator()